import java.util.*;

//课程表
public class SubjectTable {
}

//numCourses表示课程数，prerequisites记录了当前课程需在对应课程上完后才能进行，判断所有课是否能上完
//深度优先遍历，根据当前课程找到之前需要完成课程，依次向下寻找，中间出现环停止判断，返回false
class SubjectTableSolution {
    int[] record;//记录能够完成的课程，遍历到该课程直接返回true
    HashMap<Integer, List<Integer>> map;//记录所有课程对应提前需完成的课程
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        record = new int[numCourses];
        Stack<Integer> stack = new Stack();
        map = new HashMap();
        for(int[] pre:prerequisites){
            List<Integer> list = map.getOrDefault(pre[0],new ArrayList());
            list.add(pre[1]);
            map.put(pre[0],list);
        }
        for(int i=0;i<numCourses;i++){
            if(!dfs(new int[numCourses],i))return false;
        }
        return true;
    }
    boolean dfs(int[] path,int cur){//path记录当前深度遍历的节点，出现重复即成环，返回false
        if(!map.containsKey(cur)||record[cur]==1)return true;//有记录课程或课程没有限制，直接返回true
        if(path[cur]==1)return false;//成环
        path[cur] = 1;
        List<Integer> list = map.get(cur);
        for(int num:list){
            if(!dfs(path,num))return false;
            record[num] = 1;//num节点深度遍历成功，记录课程能完成
        }
        return true;
    }
}